import java.util.HashMap;
import java.util.Map;

/**
 * 460. LFU 缓存
 * https://leetcode-cn.com/problems/lfu-cache/
 */
public class Solutions_460 {
    public static void main(String[] args) {
        LFUCache lFUCache = new LFUCache(2);
        lFUCache.put(1, 1);
        lFUCache.put(2, 2);
        int res1 = lFUCache.get(1);  // output: 1
        System.out.println(res1);
        lFUCache.put(3, 3);   // 去除键 2
        int res2 = lFUCache.get(2);  // output: -1（未找到）
        System.out.println(res2);
        int res3 = lFUCache.get(3);  // output: 3
        System.out.println(res3);
        lFUCache.put(4, 4);   // 去除键 1
        int res4 = lFUCache.get(1);  // output: -1（未找到）
        System.out.println(res4);
        int res5 = lFUCache.get(3);  // output: 3
        System.out.println(res5);
        int res6 = lFUCache.get(4);  // output: 4
        System.out.println(res6);

//        LFUCache lFUCache = new LFUCache(3);
//        lFUCache.put(2, 2);
//        lFUCache.put(1, 1);
//        int res1 = lFUCache.get(2);  // output: 2
//        System.out.println(res1);
//        int res2 = lFUCache.get(1);  // output: 1
//        System.out.println(res2);
//        int res3 = lFUCache.get(2);  // output: 2
//        System.out.println(res3);
//        lFUCache.put(3, 3);
//        // put 键 4 后，将移除键 3，因为键 2 共使用了 3 次，键 1 共使用了 2 次，
//        // 键 4 共使用了 1 次，但是键 4 是最近使用过的，此时缓存中共有键 2，1，4
//        lFUCache.put(4, 4);
//        int res4 = lFUCache.get(3);  // output: -1
//        System.out.println(res4);
//        int res5 = lFUCache.get(2);  // output: 2
//        System.out.println(res5);
//        int res6 = lFUCache.get(1);  // output: 1
//        System.out.println(res6);
//        int res7 = lFUCache.get(4);  // output: 4
//        System.out.println(res7);

//        LFUCache lFUCache = new LFUCache(1);
//        lFUCache.put(2, 1);
//        int res1 = lFUCache.get(2);  // output: 1
//        System.out.println(res1);
//        lFUCache.put(3, 2);
//        int res2 = lFUCache.get(2);  // output: -1
//        System.out.println(res2);
//        int res3 = lFUCache.get(3);  // output: 2
//        System.out.println(res3);

    }
}

/**
 * 解法一：双哈希表 + 定制双向链表类 + 定制结点类（22ms）
 */
class LFUCache {
    // 定制双向链表类
    class DListNode_460 {

        private Node_460 dummyHead = null;
        private Node_460 dummyTail = null;

        public DListNode_460() {
            // 为双向链表建立虚拟的头尾结点，保证其他结点的操作不会发生空指针
            dummyHead = new Node_460();
            dummyTail = new Node_460();
            dummyHead.next = dummyTail;
            dummyTail.prev = dummyHead;
        }
    }

    // 定制结点类
    class Node_460 {
        // 键
        private int key;
        // 值
        private int val;
        // 在双向链表中对应的前驱结点
        private Node_460 prev;
        // 在双向链表中对应的后继结点
        private Node_460 next;
        // 该键的使用频次（随着键的回收而清零使用频次）
        private int freq = 0;

        public Node_460() {

        }

        public Node_460(int key, int val, int freq) {
            this.key = key;
            this.val = val;
            this.freq = freq;
        }
    }

    private int capacity = 0;
    // 最少使用次数，移除时，移除 freqMap.get(minFreq) 中的尾结点
    // minFreq 是如何变化的？当 minFreq 的双向链表长度为 0 时，表示结点的使用次数最少为 minFreq + 1 次了，那么 minFreq + 1
    private int minFreq = 1;
    // key：使用频率，value：双向链表，链表中的结点是使用频率为 key 的各个 node 结点对象
    private Map<Integer, DListNode_460> freqMap = null;
    // key：存储的键，value：对应的键值及相关数据，keyMap 存储的元素即是缓存的元素
    private Map<Integer, Node_460> keyMap = null;

    public LFUCache(int capacity) {
        this.capacity = capacity;
        freqMap = new HashMap<>();
        keyMap = new HashMap<>();
    }

    public int get(int key) {
        Node_460 node = keyMap.get(key);
        if (node == null) {
            // 查询的结点不存在于 keyMap 中，即不在缓存中
            return -1;
        }
        int freq = node.freq;
        // 从原有频次的双向链表中删除
        removeNodeAtDListNode(node);
        // 关键：先移除，再进行频次加 1
        node.freq = freq + 1;
        // 添加到频次加 1 的双向链表的头部
        addNodeToDListNode(node, node.freq);
        return node.val;
    }

    public void put(int key, int value) {
        if (capacity == 0) {
            // 提前结束：缓存为 0 时，不做操作，因为无法缓存数据，新增了结点也会被立马删除
            return;
        }
        Node_460 node = keyMap.get(key);
        if (node != null) {
            // 缓存中存在 key
            // 变更其 val
            node.val = value;
            int freq = node.freq;
            // 从原有频次的双向链表中删除
            removeNodeAtDListNode(node);
            // 添加到频次加 1 的双向链表的头部
            node.freq = freq + 1;
            addNodeToDListNode(node, node.freq);
        } else {
            // 缓存中不存在 key，需要新增一个结点
            if (keyMap.size() == capacity) {
                // 缓存将超出，先移除最不经常使用的结点，即 minFreq 频次对应双向链表的尾结点
                DListNode_460 dListNode = freqMap.get(minFreq);
                Node_460 deleteNode = dListNode.dummyTail.prev;
                // 缓存 map 中删除，同时双向链表中删除
                keyMap.remove(deleteNode.key);
                removeNodeAtDListNode(deleteNode);
            }
            // 新建结点，初始频次为 1
            Node_460 newNode = new Node_460(key, value, 1);
            // 新结点添加到频次为 1 的双向链表的头部
            addNodeToDListNode(newNode, 1);
            keyMap.put(key, newNode);
            // 关键：最后才改变 minFreq 的值，以免新增的结点立马被删除掉
            minFreq = 1;
        }
    }

    /**
     * 将结点添加到频次为 1 的双向链表的头部
     */
    public void addNodeToDListNode(Node_460 newNode, int freq) {
        DListNode_460 freqListNode = freqMap.get(freq);
        if (freqListNode == null) {
            // 频次为 freq 的双向链表不存在时，新建双向链表，并映射到 freqMap 中
            // 表示使用频次为 freq 的键，一率存储到 freListNode 中
            freqListNode = new DListNode_460();
            freqMap.put(freq, freqListNode);
        }
        // 添加 newNode 结点到 freqListNode 双向链表头部
        addNodeToHead(freqListNode, newNode);
    }

    /**
     * 添加 node 结点到 DListNode 双向链表头部
     */
    public void addNodeToHead(DListNode_460 dListNode, Node_460 node) {
        // 对应好前驱结点和后继结点
        node.next = dListNode.dummyHead.next;
        node.prev = dListNode.dummyHead;

        node.next.prev = node;
        node.prev.next = node;
    }

    /**
     * 完成 node 结点在所在双向链表中的删除
     */
    public void removeNodeAtDListNode(Node_460 node) {
        // 获取到当前结点的使用频次
        int nodeFreq = node.freq;
        Node_460 next = node.next;
        Node_460 prev = node.prev;
        // 分别将 node 的前驱结点的后继结点指向 node 的后继结点，将 node 的后继结点的前驱结点指向 node 的前驱结点
        prev.next = next;
        next.prev = prev;
        // 判断所在双向链表移除 newNode 后，链表长度是否为 0
        DListNode_460 dListNode = freqMap.get(nodeFreq);
        if (isEmpty(dListNode)) {
            // 双向链表长度为 0，从 freqMap 中移除（）
//            freqMap.remove(nodeFreq);
            if (nodeFreq == minFreq) {
                // 最少使用频次的链表长度为 0，那么下次移除缓存元素时，就要从 minFreq + 1 的双向链表的尾部中移除了
                minFreq ++;
            }
        }
    }

    /**
     * 判断双向链表 dListNode 长度是否为 0
     */
    public boolean isEmpty(DListNode_460 dListNode) {
        // 除虚拟结点外，已经没有其他结点时，链表长度为 0
        return dListNode.dummyHead.next == dListNode.dummyTail;
    }
}
